
struct ListNode
{
    int val;
    struct ListNode* next;
    ListNode(int x)
        : val(x), next(nullptr)
    {}
};

class Solution2
{
public:
    ListNode* addInList(ListNode* head1, ListNode* head2)
    {
        ListNode* l1 = dfs(head1);
        ListNode* l2 = dfs(head2);

        ListNode* cur1 = l1, * cur2 = l2;
        ListNode* newhead = new ListNode(-1);
        int next = 0;
        while (cur1 || cur2 || next == 1)
        {
            int val1 = cur1 == nullptr ? 0 : cur1->val;
            int val2 = cur2 == nullptr ? 0 : cur2->val;
            int mul = val1 + val2 + next;
            next = mul / 10;
            mul %= 10;
            ListNode* node = new ListNode(mul);
            node->next = newhead->next;
            newhead->next = node;
        }
        return newhead->next;
    }

    ListNode* dfs(ListNode* head)
    {
        if (head == nullptr || head->next == nullptr) return head;

        ListNode* newhead = dfs(head->next);
        head->next->next = head;
        head->next = nullptr;

        return newhead;
    }
};